package bintree.nowcoder;

/**
 * 二分搜索树转为双向链表
 */
public class ConvertTreeDemo {
    // 传入一颗BST，就能返回排序后的双向链表的链表头
    public TreeNode Convert(TreeNode pRootOfTree) {
        // 空树或者只有根节点
        if (pRootOfTree == null || (pRootOfTree.left == null && pRootOfTree.right == null)) {
            return pRootOfTree;
        }
        // 1.先将左树转换为双向链表
        TreeNode left = Convert(pRootOfTree.left);
        // 2.找到左树的尾节点
        TreeNode leftTail = left;
        while (leftTail != null && leftTail.right != null) {
            leftTail = leftTail.right;
        }
        // 3.将左树与根节点相连
        if (left != null) {
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        // 4.再将右树转为双向链表
        TreeNode right = Convert(pRootOfTree.right);
        // 5.将右树与根节点连接
        if (right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        // 6.返回整个链表
        return left == null ? pRootOfTree : left;
    }
}
